// https://www.lintcode.com/problem/minimum-adjustment-cost

public class Solution {
    /*
     * @param A: An integer array
     * @param target: An integer
     * @return: An integer
     */
    public int MinAdjustmentCost(List<Integer> A, int target) {
        // write your code here
        /*
        动态规划，重要的限制条件是最大的数小于等于100！
        我们用d[i][j]表示第i个元素调整到j的最小代价。所以最后结果就是d[i][0]到d[i][100]取最小值。
        */
        if (A.size() < 2) {
            return 0;
        }
        int[][] costs = new int[A.size()][101];
        for (int i = 0; i < A.size(); ++i) {
            Arrays.fill(costs[i], Integer.MAX_VALUE);
        }
        for (int i = 0; i <= 100; ++i) {
            costs[0][i] = Math.abs(A.get(0) - i);
        }
        for (int i = 1; i < A.size(); ++i) {
            for (int j = 0; j <= 100; ++j) {
                int diff = Math.abs(A.get(i) - j); // A[i]调整到j的成本
                int begin = Math.max(0, j - target); // 计算A[i]调整到j的上下限
                int end = Math.min(100, j + target);
                for (int k = begin; k <= end; ++k) {
                    /*
                    重点！！！
                    cost[i - 1][k]代表第A[i - 1]调整到j的最小代价
                    k + diff - A[i] + dff确保调整后范围在target内
                    */
                    costs[i][j] = Math.min(costs[i][j], costs[i - 1][k] + diff);
                }
            }
        }
        int ret = Integer.MAX_VALUE;
        for (int i = 0; i <= 100; ++i) {
            ret = Math.min(ret, costs[A.size() - 1][i]);
        }
        return ret;
    }
}